package huffmancode;

import java.io.*;
import java.util.*;

/**
 * 哈夫曼编码(压缩和解压)
 */
public class HaffmanCode {
    public static void main(String[] args) {
//        String content = "i like like like jave do you like a java";
//        byte[] contentBytes = content.getBytes();  //字节数组
//
//        //打印字节数组
//        System.out.println("字符串对应的字节数组："+Arrays.toString(contentBytes));
//
//        byte[] bytes = huffmanZip(contentBytes);
//        System.out.println("对应的编码后的字节数组："+Arrays.toString(bytes));
//
//        System.out.println("解码：-------------");
//        byte[] decode = decode(huffmanCodes, bytes);
//        System.out.println(new String(decode));

//        //测试压缩文件
//        String path = "H://test.txt";
//        String s_path = "H://test.zip";
//
//        zipFile(path,s_path);


        //测试解压文件
        String path = "H://test.zip";
        String s_path = "H://jieya.txt";
        unZipFile(path,s_path);




    }

    /**
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return 经过哈夫曼编码后的字节数组
     */
    private static byte[] huffmanZip(byte[] bytes){
        List<Node> nodes = getNodes(bytes); //得到字符和权值
        Node huffmanTree = createHuffmanTree(nodes);  //构建哈夫曼树
        Map<Byte, String> huffmanCodes = getCodes(huffmanTree); //生成对应的哈夫曼编码
        byte[] zip = zip(bytes, huffmanCodes);  //压缩得到压缩后的哈夫曼编码字节数组

        return zip;

    }

    /**
     *  生成哈夫曼编码
     * @param bytes  原始的字符串对应的byte[]
     * @param huffmanCodes  生成哈夫曼编码的map
     * @return  返回处理后的byte[]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {

        //利用huffmanCodes 将byte转化为哈夫曼编码字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println(stringBuilder.toString());
        //将100010100101001....转化为byte[]，每8位存放一下
        int len; //每8位可以存多少次
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建一个存储压缩后的byte数组(8个8个放入字节数组)
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0; //记录是第几个byte
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;

            if (i + 8 > stringBuilder.length()) {//不够8位了
                strByte = stringBuilder.substring(i); //从当前位置取到最后
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }

            //将strByte转成byte
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte,2); //把二进制转化为十进制
            index++;

        }
        return huffmanCodeBytes;
    }

    //生成哈夫曼树对应的哈夫曼编码
    //将哈夫曼编码表存放在Map<Byte,String> 形式a=100 d=11000(数据和叶子节点的路径)
    static Map<Byte,String > huffmanCodes = new HashMap<Byte, String>();
    //在找到叶子节点时，需要保存路径，定义一个StringBuilder 存储某个叶子节点路径
    static StringBuilder stringBuilder = new StringBuilder();

    //重载getCodes方法
    private static Map<Byte, String> getCodes(Node root){
        if(root ==null){
            return null;
        }
        getCodes(root,"",stringBuilder);
        System.out.println("每个字符对应的路径："+huffmanCodes);
        return huffmanCodes;
    }


    /**
     * 将传入node节点的所有叶子节点的哈夫曼编码得到，放入到huffmanCodes集合中
     * @param node 传入节点（root节点）
     * @param code 路径  规定向左为0 向右为1
     * @param stringBuilder  用于拼接路径
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder){

        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);  //相当于拼接的操作
        //将 Code 加入到 stringBuilder2 中
        stringBuilder2.append(code);
        if(node !=null){ //如果node == null不处理
            //判断node是不是叶子节点
            if(node.data ==null){ //非叶子节点
                //递归处理(向左)
                getCodes(node.left, "0", stringBuilder2);
                //向右递归
                getCodes(node.right,"1",stringBuilder2);
            }else{ //说明时叶子节点
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }
    }


    //前序遍历方法
    private static void preOrder(Node root){
        if(root !=null){
            root.preOrder();
        }else{
            System.out.println("哈夫曼树为空");
        }
    }


    //返回得到ArrayList数组，每个元素代表一个节点，包含数据和权值
    private static List<Node> getNodes(byte[] bytes){
        //创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();

        //统计每个字节出现的次数
        HashMap<Byte, Integer> counts = new HashMap<Byte, Integer>();
        for (byte b:
             bytes) {
            Integer count = counts.get(b);
            if(count == null){  //Map还没有这个数据
                counts.put(b,1);
            }else{
                counts.put(b,count+1);
            }
        }

        //把每一个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for(Map.Entry<Byte,Integer> entry : counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    //通过List 创建一个哈夫曼树
    /**
     *
     * @param nodes 通过传入的list中的nodes来创建哈夫曼树
     * @return
     */
    private static Node createHuffmanTree(List<Node> nodes){
        while (nodes.size()>1){
            //排序
            Collections.sort(nodes);

            //先取前面两个
            Node leftnode = nodes.get(0);
            Node rightnode = nodes.get(1);

            //创建一棵新的二叉树,根节点没有data,只有权值
            Node parent = new Node(null, leftnode.weight + rightnode.weight);
            parent.left = leftnode;
            parent.right = rightnode;

            //将处理过的二叉树移除
            nodes.remove(leftnode);
            nodes.remove(rightnode);

            //将新的二叉树计入到nodes
            nodes.add(parent);
        }
        return nodes.get(0);
    }


    //完成数据的解压
    //1.先将生成后的哈夫曼字节数组转化为二进制  “10101001010010....”
    //2.对照哈夫曼数据，权值那个数组进行解压

    //完成对压缩数据的解码
    /**
     *
     * @param huffmanCodes 哈夫曼编码表
     * @param huffmanBytes 哈夫曼编码得到的字节数组
     * @return 原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        //先得到这个huffmanBytes 对应的二进制的字符串形式 “10101001001...”
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1); //成立代表最后一个元素
            stringBuilder.append(byteToBitString(!flag, b));
        }
//        System.out.println("解码后的二进制：" + stringBuilder.toString());

        //把字符串按照指定的哈夫曼编码进行解码
        //把哈夫曼表进行调转，原来是a->100, 现在要 100->a
        Map<String, Byte> map = new HashMap<String, Byte>();
        //遍历原来的哈夫曼表(将键值对反过来)
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
//        System.out.println(map);

        //创建一个集合存放byte
        List<Byte> list = new ArrayList<Byte>();
        for (int i = 0; i < stringBuilder.length();) { //不停扫描二进制字符串，进行比对

            int count = 1; //一个小的计数器
            boolean flag = true;
            Byte b = null;

            while (flag) {

                //取出一个1或者是0
                //i不动，count一个一个走，直到匹配到一个字符
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    //说明没有匹配到
                    count++;
                } else {
                    //匹配到
                    flag = false;
                }
            }
            list.add(b);  //将匹配到的字符加入到list中

            i += count;  //将i直接移动到count的位置
        }
        //把list中的数据放入到byte[]中进行返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i <b.length ; i++) {
            b[i] = list.get(i);
        }

        return b;
    }
    /**
     * 将一个byte转化为一个二进制字符串
     * @param b 哈夫曼编码字节数组
     * @param flag 标识是否需要补高位，true表示需要补高位
     * @return  该byte对应的二进制字符
     */
    private static String byteToBitString(boolean flag, byte b){
        //使用一个变量保存b
        int temp = b;  //将 b 转化为 int
        //如果是正数，我们还存在补高位
        if(flag){
            temp |=256;
        }

        String str = Integer.toBinaryString(temp);
        if(flag){
            return str.substring(str.length()-8);  //取后面8位
        }else{
            return str;
        }

    }

    //编写一个方法，将一个文件进行压缩
    /**
     *
     * @param srcFile 你希望压缩的文件的全路径
     * @param dstFile 压缩后将压缩文件放到那个路径
     */
    public static void zipFile(String srcFile,String dstFile){

        //创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;

        //创建文件的输入流
        FileInputStream is = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]数组,is.available()文件长度
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);

            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);

            //创建文件的输出流，存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流相关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把哈夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes); //先把

            //这里我们以对象流的方式写入哈夫曼编码，是为了以后我们恢复源文件时使用
            //一定要把哈夫曼编码写入压缩文件
            oos.writeObject(huffmanCodes);

        } catch (Exception e) {
            System.out.println(e.getMessage());
        }finally {

            try {
                is.close();
                oos.close();
                os.close();
                System.out.println("压缩完成！");
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }


    //完成对压缩文件的解压

    /**
     *
     * @param zipFile  准备解压的文件
     * @param dstFile  将文件解压到那个路径
     */
    public static void unZipFile(String zipFile, String dstFile){
        //定义文件的输入流
        InputStream is = null;
        //定义与对象输入流
        ObjectInputStream ois = null;
        //定义一个文件的输出流
        OutputStream os = null;

        //创建文件输入流
        try {
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            ois = new ObjectInputStream(is);

            //读取压缩后的字节数组
            byte[] huffmanBytes = (byte[])ois.readObject();

            //读取哈夫曼编码表
            Map<Byte,String> huffmanCodes = (Map<Byte, String>) ois.readObject();
            System.out.println(huffmanCodes);

            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);

            //写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到文件中
            os.write(bytes);

        } catch (Exception e) {
            System.out.println(e.getMessage());
        }finally {
            try {
                is.close();
                os.close();
                ois.close();
                System.out.println("解压完成！");
            } catch (IOException e) {
                e.printStackTrace();
            }

        }
    }
}

//创建一个Node,存放数据和权值
class Node implements Comparable<Node>{
    Byte data;  //存放数据本身，比如 ‘m’,其实是ascll码
    int weight; //权值，表示字符出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    //前序遍历
    public void preOrder(){
        System.out.println(this);
        if(this.left !=null){
            this.left.preOrder();
        }
        if(this.right !=null){
            this.right.preOrder();
        }
    }
}
